/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhongfang
 *
 */
public class CoinPath {
    public List<Integer> cheapestJump(int[] A, int B) {
    	int n=A.length;
        int dp[]=new int[n];
        final int MAX=Integer.MAX_VALUE;
        ArrayList<Integer> result=new ArrayList<>();
        if(A[0]==-1||A[n-1]==-1){
        	return result;
        }
        int maxLianXu=0;
        for (int i = 0; i < n; i++) {
        	int tmp=0;
			while (i<n&&A[i]==-1) {
					i++;
					tmp++;
			}
			if(tmp>maxLianXu){
				maxLianXu=tmp;
			}
		}
        if(maxLianXu>=B){//impossible
        	return result;
        }
        dp[0]=A[0];
        ArrayList<Integer> [] intLists=new ArrayList[n];
        intLists[0]=new ArrayList<>();
        intLists[0].add(1);
        for (int i = 1; i < n; i++) {
			if(A[i]==-1){
				dp[i]=MAX;
			}else {
				int min=MAX;
				ArrayList<Integer> intListTmp=null;//对应最小字典序路径
				for (int j = i-1; j >=i-B&&j>=0; j--) {
					if(A[j]==-1){
						continue;
					}
					if(min>dp[j]){
						min=dp[j];
//						System.out.println("----------------------------dp--old"+intListTmp+" xin "+intLists[j]);
						intListTmp=new ArrayList<>(intLists[j]);
					}else if (min==dp[j]) {//选取字典序最小的路径
						int minLen=Math.min(intListTmp.size(), intLists[j].size());
						int k = 1;
						for (; k < minLen; k++) {
							if(intListTmp.get(k)<intLists[j].get(k)){
								break;
							}else if (intListTmp.get(k)>intLists[j].get(k)) {
//								System.out.println("--------------------------字典序----old"+intListTmp+" xin "+intLists[j]);
								intListTmp=new ArrayList<>(intLists[j]);
								break;
							}
						}
					}
				}
				intListTmp.add(i+1);
				intLists[i]=intListTmp;
				dp[i]=min+A[i];
//				System.out.println(i+1);
			}
		}
        return intLists[n-1];
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] A={36,53,77,73,93,60,49,47,36,48,70,3,76,18,45,75,5,23,50,65,84,61,40,-1,41,15,58,0,73,78,76,41,6,15,45,33,93,45,54,32,37,88,88,24,59,30,8,64,97,78,74,8,74,44,59,20,80,65,97,54,40,82,79,30,62};
//		System.err.println(A.length);
		int B=8;
		System.out.println(new CoinPath().cheapestJump(A, B));
	}

}
